The present invention relates to computer network devices, and more particularly to memories used in crossbar and other packet switches.
Packet switches are well known and widely used to route packets from one host to another. A packet switch, such as packet switch 10 shown in FIG. 1, includes a multitude of input (ingress) ports 12, a multitude of output (egress) ports 14, and a switch fabric 16. Each packet is received via one of the input ports 12 and forwarded to one or more of the output ports 14 based on the packet's forwarding address information. During each packet time, each one of the input ports is in communication with one or more of the output ports. Contention occurs if the arrival rate of the packets destined for any of the output ports exceeds the capacity of that output port to receive them.
To prevent packet loss, a switch packet must include queues. The queues may be located at the switch input ports in accordance with the input queuing technique, or at the switch output ports in accordance with the output queuing technique. In switches using the input queuing technique, incoming packets are stored in the input queues as they arrive. The packets at the top (front) of the queues are thereafter forwarded to their destination output ports. If the packets at the front of several different input ports are destined for the same output port at the same time, then only one of them can be forwarded. Packets not forwarded to their destination remain in the queue and may potentially block other packets from reaching their destination. This effect is commonly known as head-of-line blocking. For example, in FIG. 2, a packet destined for port 1 is shown as being blocked by a packet contending for port 2.
One known method for overcoming the head-of-line blocking is to use output queuing. In one implementation of the output queuing, an egress queue is dedicated to every source port in every output. Incoming cells are forwarded through the switch and queued at the egress ports. In the output queuing technique, the bandwidth of the memory at every output increases linearly with the number of input ports. However, the number of memory instances at the output grows at least as fast as n2, where n is the number of input/output ports. Because of this n2 relationship, this technique is not scalable as the number of ports increases.
FIG. 3 shows a crossbar switch having three output ports 75, 85, 95, three input ports 70, 80, 50, and a shared memory 65. During each cell time, shared memory 65 receives and stores data from the three input ports 70, 80, 50, and supplies data to the output ports 75, 85, 95. Therefore, shared memory 65 is required to support a bandwidth six times the aggregate bandwidth of each of the input/output ports. For example, if each of the input/output ports is a 10 gigabit/second port, shared memory 65 is required to have a bandwidth of 60 gigabit/second. Supporting such high bandwidths as the number of ports increases poses a number of difficult challenges.
In an article entitled “A Highly Modular Packet Switch For GB/Rates”, by W. E. Denzel, A. P. J. Engbersen, I. Iliadis, an, and G. Karlsson, IBM Research Division, Zurich Research Laboratory, 8803 Ruschlikon, Switzerland, International Switching Symposium, Oct. 25-30, 1992, pp. 236-240, authors Denzel et al. described a new memory architecture for a broadband switching device. FIG. 4 is a block diagram of a cell memory 100 described by Denzel et al. In the following, it is understood that the terms packets and cells may be collectively and interchangeably referred to as packets. Cell memory 100 has a memory width defined by the following:M×Prate×Tacc×2where M represents the number of cells that the memory can store at any given time, Prate represents the port rate, and Tacc represents the memory access time. The product of M, Prate, and Tacc is multiplied by 2 to account for the fact that during each clock cycle, the memory is accessed to perform both a read operation and a write operation. For example, assuming that the port rate is 10 Gb/sec, the memory access time is 2.5 nsec, and the memory is adapted to store 1000 cells at any given time, the memory is 50000 bits wide. The memory depth is defined by the cell length as well as the following:Prate×Tacc×2
For example, assuming that each cell has a length of 100 bytes, and that each addressable memory location is configured to store 50 bits for each cell, the memory depth is (100×8/50)=16. In other words, for the above example, the memory has 16 addressable locations.
Referring to FIG. 4, packets (cells) arriving at the input ports are routed through 1-to-M routers into the cell memory 100. These routers are 1-to-M demultiplexers each responsible for transferring the packet arriving at its input into an empty storage location. Thus all Ni routers can transfer a packet to a storage location at any given time. Packets leaving the switch are routed from the memory through M-to-1 selectors to the output ports. There is a selector for each of the No output ports. These selectors constitute M-to-1 multiplexers which route packets from the proper storage locations to the designated output ports. Accordingly, each packet is stored across the memory depth occupying, e.g., only one bit of each memory word. The memory organization shown in FIG. 4 is adapted to support packets having a fixed size. A need continues to exist for a memory organization that has high-aggregate throughput and that is adapted to handle packet or cell sizes of varying lengths.